1. Field of the Invention
The present invention relates to a packet multiplexing apparatus for multiplexing packets input from a plurality of input ports and outputting to one output port, and to a method of operating in a communication system comprised by a plurality of network communication facilities connected by branching transmission lines to an opposite local service node.
This application is based on patent application Nos. Hei 2-110954 and Hei 10-110777 filed in Japan, the contents of which are incorporated herein by reference.
2. Description of the Related Art
For conventional packet multiplexing apparatus, the round robin method is applied. In this method, input ports are checked for the presence or absence of packets starting from an input port with a low port number.
The round robin method will be explained with reference to FIG. 10. The packet multiplexing apparatus has n input ports (n is an integer larger than 2) 1-0xcx9c1-(nxe2x88x921) and an output port 2. The input ports are sequentially numbered. In this case, an input port 1-0 designates an input port in location 0, 1-1 in location 1, and similarly input port 1-(nxe2x88x921) in location (nxe2x88x921). Each input port is provided with respective buffer memories 3-0 to 3-(nxe2x88x921). The output signal transmission circuit 4 checks whether the packets are stored in individual buffer memories in the order of increasing port number, and if there is a packet, this packet is sent to output port 2, while if there is no packet, it checks the next buffer memory corresponding to the next higher port number. This is the method of multiplexing used in the conventional packet multiplexing apparatus to multiplex packets input from input ports 1-0xcx9c1-(nxe2x88x921) and outputting multiplexed packets to output port 2.
In the round robin method, when there is an input port that is outputting packets frequently, the input port that is immediately behind the busy port must wait a longer period on average for its packet to be retrieved, compared with the input port immediately ahead of the busy input port. Therefore, differences in the waiting time results for the various input ports.
When operating in a public network system, it is necessary to guarantee fairness of service to all the users connected through individual input ports. However, conventional round robin method could not assure uniform treatment of all input ports.
This problem of unfair packet retrieval will be explained in more detail using an example shown in FIG. 10. Suppose that m is an integer smaller than (nxe2x88x921), and consider a case that packets are being input in (m)th input port at a higher rate than other input ports which are relatively idle. Waiting times of packets in (mxe2x88x921)th port and (m+1)th port will be compared in the following.
When a packet arriving in (mxe2x88x921)th input port can be sent immediately to output port 2, if, (m)th input port is not busy. In comparison, a packet arriving in (m+1)th input port can be sent immediately to output port 2 when (m)th input port is not busy and, additionally, when its buffer memory for (m)th input port is vacant in the next round of checking the (m)th input port. For this reason, the probability of immediate packet output from (m+1)th input port is lower than that from (mxe2x88x921)th input port. In other words, the average waiting time for sending a packet is longer for a port that is ahead of the busy (m)th input port, i.e. (m+1)th input port, relative to a port that is behind the busy (m)th input port m, i.e. (mxe2x88x921)th input port.
Therefore, an inherent problem exists in the round robin method that fairness in accessing one output port cannot be guaranteed for all users, in a communication system dependent on conventional packet multiplexing apparatus using round robin method.
One example of systems that utilizes such a packet multiplexing apparatus is a communication system comprised by a plurality of network communication facilities (users) oppositely connected to a local service node (local exchange) through branching transmission lines.
A communication method using such a system will be explained below.
FIG. 11 shows an example of the foregoing communication system including n network communication (com) facilities 110-1xcx9c110-n (where n is an integer larger than 2) and a local service node 120 connected through a star coupler 130 with a branching ratio of n:1. That is, network com facilities 110-1xcx9c110-n having dedicated optical fiber lines 140-1xcx9c140-n are connected in a n:1 ratio through a star coupler 130 to a local service node 120 having an optical fiber line 150. In other words, the local service node 120 is being shared by a plurality of network com facilities 110-1xcx9c110-n.
Each of the network corn facilities 110-1xcx9c110-n includes network termination units 111-1xcx9c110-n for optical-electrical signal conversion and for termination of the signals exchanged between the local service node 120 and the network com facilities 110-1xcx9c110-n, and service-function interface units. This example relates to a case of multiplexing of call connections for connection to the trunk network and LAN connections. In this example, interface units are comprised by circuit interfaces 112-1xcx9c112-n and LAN interfaces 113-1xcx9c113-n. Circuit interfaces 112-1xcx9c112-n are connected to respective telephones 114-1xcx9c114-n, and LAN interfaces 113-1xcx9c113-n are connected to respective computers or line hubs 115-1xcx9c115-n.
The local service node 120 is comprised by: local line termination units 121-1xcx9c121-n for optical-electrical signal conversion and for termination of signals exchanged between the local service node 120 and network corn facilities 110-1xcx9c110-n; a cross connect (XC) unit 122; and the interface units. Similar to the network com facilities, an interface unit is comprised by a circuit interface 123 and a LAN interface 124. The circuit interface 123 is connected to an exchanger 125, and the LAN interface 124 is connected to a router 126.
A method of communication in such a branched transmission line is to use a time compression multiplexing (TCM) method, in which upward signals (from network com facilities to the local service node) and downward signals (from the local service node to network com facilities) are transmitted through the same line but are identified by the differences in their positions on a common time base.
FIG. 12 shows a communication diagram, showing the signal exchanges between the network com facilities 110-1xcx9c110-n and the local line termination unit 121, according to the conventional communication method. For simplification, only the case of LAN connection will be explained. Also for simplification, synchronizing frames for the communication channel and optical transmission delay times through optical fibers are omitted. In the case of LAN connection, network com facilities 110-1xcx9c110-n share a channel for transmitting the signals.
In this case, transmission and reception of signals are performed in burst cycles, that is, repeated cycles of transmission and reception actions. In a burst cycle, the downward signal channel (for transmitting downward signals from the local line termination unit 121 to the network com facilities 110-1xcx9c110-n) and the downward com channel shared by the network com facilities are processed in the time division multiplexing (TDM) mode in the downward channel. And, in the upward channel, upward signal channels, for transmitting signals from the network com facilities 110-1xcx9c110-n to the local line termination unit 121, and the upward com channel shared by the network com facilities are similarly processed in the TDM mode.
The example in FIG. 12 shows that four network com facilities 110-1xcx9c110-n share one upward corn channel. In order to share the com channel by four network com facilities, those facilities having the data to be sent output respective frame allocation requests to the local line termination unit 121. Responding to the frame allocation requests, the local line termination unit 121 issues a frame transmission approval to each of the requesting facilities. In order to increase the volume of data from a plurality of users that can be transmitted in the upward corn channel, each network com facility includes in the frame allocation request, the information regarding the amount of data to be sent, and the local line termination unit includes, in the frame allocation approval, the information regarding the frame transmission timing and an approved length of frames for transmission.
According to the conventional method of communication, therefore, when the upward com channel is to be shared by the a number of network com facilities, the local line termination unit controls the timing of outputting the user data to the upward com channel and the amount of usage in the upward com channel, and based on the results of such control actions, it is necessary to inform the user facilities on the timing and channel use information. This methodology requires the local line termination unit to use a high-speed control device for performing complex control actions quickly, and a circuitry of a large scale operating at a high-speed so that a large amount of data should be handled.
An object of the present invention is to provide a packet multiplexing apparatus that guarantees an equal access to one output port from a plurality of input ports, by substantially equalizing the waiting time for a packet to be retrieved from each input port. Another object of the present invention is to achieve the same by allocating an equal bandwidth to each input port.
In the conventional round robin method of packet multiplexing, the order of retrieving packets from input ports is unchanged in all retrieval rounds. This inherent problem in the conventional method is remedied in the present invention by changing the order of retrieving the packets from successive input ports for each round of packet retrieval.
In the present apparatus, the retrieval process is controlled so that the order of retrieving packets from the input ports is allocated to each port (of port 1 to port n) at an identical probability from retrieval 1 to retrieval n, where n is an integer larger than 2.
Furthermore, the retrieval process is controlled so that the frequency of any input port to be placed behind a packet-outputting-port is the same for all input ports 1 to n. In other words, the retrieval method can assure that, even if there is an input port that outputs packets frequently, it can be assured that a particular input port will not always be behind this busy input port. Therefore, each input port is given an equal waiting time before its packet is retrieved.
Also, the retrieval process is controlled so that a total length of packets retrieved from a buffer memory will be less than a specific length for all buffer memories. Or, a ring buffer can be used for each input port so that packets having tail data within a region of the ring buffer will all be retrieved in the order of their arrival. Such a method enables to equalize the bandwidth of all input ports operating within the system.
Another object of the present invention is to provide a method of communication in a communication system comprised by a number of network communication facilities connected oppositely through a branching lines to one local server node, using circuits of a small scale and without the need for high-speed controls.
The feature of the present method is that at least two frame packets to be shared by each network communication facility are defined within one burst cycle for upward communication, and frame packets are allocated to the users in frame packet units.
This method simplifies allocation processing, because it is only necessary to respond to a network facility by instructing the location of the frame packets to be used, thereby eliminating the need for high-speed control devices for undertaking complex control functions required in the conventional method. Thus, the present packet multiplexing apparatus and method enable to manage communication tasks at high-speed based on control circuits of a much smaller scale.